package prefixTree;

/**
 * 题目 :神奇字典
 * 题目详述 ：
 * 设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。
 * 如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于已构建的神奇字典中。
 *
 * 实现 MagicDictionary 类：
 * MagicDictionary() 初始化对象
 * void buildDict(String[]dictionary) 使用字符串数组dictionary 设定该数据结构，dictionary 中的字符串互不相同
 * bool search(String searchWord) 给定一个字符串 searchWord ，
 * 判定能否只将字符串中 一个 字母换成另一个字母，使得所形成的新字符串能够与字典中的任一字符串匹配。
 * 如果可以，返回 true ；否则，返回 false 。
 */
public class MagicDictionary {
    /**
     * 核心思想 ：
     * （1）首先，初始化前缀树，将所要插入的单词插入到前缀树中；
     */
    TrieNode root; // 设置前缀树根节点为全局变量，即能够被当前类中的任何方法进行使用；
    public MagicDictionary() {
        // 初始化前缀树根节点
        root = new TrieNode();
    }
    // 初始化前缀树
    public void buildDict(String[] dictionary) {
        for (String word : dictionary) {
            // 每次遍历词典中的单词都需要从根节点进行遍历，所以需要定义一个零临时变量，来存储前缀树中根节点的值；
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                if(node.children[c - 'a'] == null){
                    node.children[c - 'a'] = new TrieNode();
                }
                node = node.children[c - 'a'];
            }
            node.isWord = true;
        }
    }

    // 所需要实现的 ：在上述词典中，当前所要寻找的字符串只要修改其自身的一个字符，就存在于词典中

    /**
     * 具体实现 ：
     * （1）深度优先遍历，即对于前缀树中每一个子节点进行递归遍历；(由于是多叉树，遍历顺序为从最左子节点开始，类似于二叉树后序遍历)
     * （2）只有满足多个条件才能够判断true；
     *      遍历前缀树长度 == 字符串长度 && 修改字符串次数 == 1 && 字符串中最后一个字符在前缀树中所对应的节点的isWord属性为true（表示其是一个单词的结尾）
     * @param searchWord
     * @return
     */
    public boolean search(String searchWord) {
        /**
         * dfs递归函数中参数解释 ：
         * （1）第一个参数 ：所传递的是当前正在遍历的前缀树节点；
         * （2）第二个参数，即代表判断其是否满足题目条件的字符串；
         * （3）第三个参数，即代表字符串中当前正在遍历的字符索引；（通俗易懂来说，就是已经遍历到字符串的那个字符）
         * （4）第四个参数，即代表了当前字符串的修改次数
         * （即，由于是深度优先搜索，会遍历到所有可能的字符串，若是原本保存的字符串和当前遍历到的字符串有两个字符不同的话，即不存在）
         */
        return dfs(root, searchWord, 0, 0);
    }

    private boolean dfs(TrieNode root, String searchWord, int index, int updateSum) {
        // 如果当前接节点不存在的话，返回值为false
        if(root == null){
            return false;
        }
        // 即，这个if条件判断，是用来判断是否寻找到符合条件的字符串；
        // 若是满足以下条件的话，即返回true；
        if (index == searchWord.length() && updateSum == 1 && root.isWord) {
            /**
             * 需要注意的是：
             * （1）由于前缀树的根节点不存储任何字符，同时，第一次使用dfs遍历时，所传入的节点即为根节点；
             * ===》 dfs递归函数，所传入的前缀树节点为对应着字符串中index - 1的字符；
             * （通俗易懂地将，就是当前dfs递归函数中所使用的前缀树节点root，是上一个递归函数中已经进行过 是否修改判断的前缀树节点）
             * （2）同时最后一次进入dfs函数判断时，所传入的前缀树节点对应的是字符串的最后一个字符 && index == 字符串长度（由于字符串是从0开始遍历）
             * && updateSum，是用来记录字符串修改次数
             * （由于所传入的前缀树节点对应的是字符串的最后一个字符，代表了字符串中每个字符对应的前缀树节点都 已经判断过是否已经进行过修改）
             */
            return true;
        }
        // 此if条件，只有满足遍历条件，才能够对前缀树中节点继续向下进行遍历；
        // 若是updateSum > 1的话，即说明当前字符串已经修改超过1次，对于后续的前缀树节点也没有必要再去遍历；
        // 若是遍历索引超过所要查询字符串的长度的话，对于后续的前缀树节点没有必要再去遍历；
        if(updateSum <= 1 && index < searchWord.length()){
            boolean flag = false;
            // 循环结束条件：（1）遍历完所有前缀树节点（2）同时若是flag为true，代表已经找到符合条件的字符串，直接跳出循环即可
            for(int i = 0 ;i < 26 && !flag;i++){
                // 当遍历到指定的前缀树中某个节点时，需要去判断其是否与对应字符串中index位置的字符是否一致；
                int sum = (i == (searchWord.charAt(index) - 'a')) ? updateSum : updateSum + 1;
                // 需要注意的是， 若是使用root.children中所存储的字符进行判断的话，可能会出现当前前缀树节点的children为null
//                int sum = (root.children[i].equals(searchWord.charAt(index))) ? updateSum : updateSum + 1;
                flag = dfs(root.children[i], searchWord , index + 1 , sum );
            }
            // 由于是递归操作，所以一旦找到符合条件的字符串的话（即，flag = true），需要将flag的结果传递回去，即需要跳出递归；
            // flag = dfs(root.children[i], searchWord , index + 1 , sum );
            // 可见，递归结果，是使用flag进行存储，若是寻找到符合条件的字符串，只需要将flag置为true，即可快速跳出递归；
            return flag;
        }
        // 若是上述条件都不满足的话，即直接返回false即可
        return false;
    }
    /**
     * 分析 ：
     * （1）最后一次dfs递归函数，所进行判断的是 所要判断字符串中最后一个字符的后一个，即不存在的字符；
     * ===》即，再此次dfs递归中，传入字符串的所有字符都已经和前缀树中的节点进行比较
     * && 获取到了在此过程中，字符串的修改次数 && 字符串中最后一个字符所对应的前缀树节点isWord属性值（即，在前缀树中其是否为一个单词）
     * （2）时间复杂度：
     * 初始化前缀树的时间复杂度：O(n*m) （其中，n为字符串数组中字符串个数；同时，m为字符串长度）；
     * dfs函数的时间复杂度：O(n) (其中，n为前缀树中节点总数)
     */
}
